package cn.caplike.demo.algorithm.tree.trie;

/**
 * Description:
 * <p>Todo: 打印前缀树的属性结构以及删除</p>
 * <p>Reference: <a href="https://pdai.tech/md/algorithm/alg-basic-tree-trie.html">Trie Tree</a></p>
 *
 * @author LiKe
 * @date 2023-06-19 10:00:20
 */
public class Trie {
    private final TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String str) {
        TrieNode current = root;
        for (int idx = 0; idx < str.length(); ++idx) {
            char c = str.charAt(idx);
            if (!current.children.containsKey(c)) {
                current.children.put(c, new TrieNode());
            }
            current = current.children.get(c);
        }
        current.setEnd(true);
    }

    private TrieNode searchPrefix(String word) {
        TrieNode current = root;
        for (int idx = 0; idx < word.length(); idx++) {
            char c = word.charAt(idx);
            if (current.children.containsKey(c)) {
                current = current.children.get(c);
            } else {
                return null;
            }
        }
        return current;
    }

    // 字符串的查找
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEnd();
    }

    //前缀的查找
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }

    public static void main(String[] args) {
        String[] a = {"一颗大苹果", "一条小黑狗", "Dream harder!"};
        Trie trie = new Trie();
        for (String s : a) {
            trie.insert(s);
        }
        System.out.println(trie.search("一颗大苹果"));
        System.out.println(trie.startsWith("she"));
    }
}
